package com.mdnote.practice.dp.stock;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/22 0022
 * @description
 */
public class LeetCode188 {

    public int maxProfit(int k, int[] prices) {
        if (k > prices.length / 2){
           return maxProfit_inf(prices);
        }
        return maxProfit_k(prices, k);
    }

    public int maxProfit_k(int[] prices, int dp_k) {

        if (prices.length <= 1) {
            return 0;
        }
        int[][][] dp = new int[prices.length][dp_k][2];

        // base case
        // 第一天没有机会，手上也没股票
        dp[0][0][0] = 0;
        // 第一天没有机会了但是持有股票，应该是吧第一天入股了
        dp[0][0][1] = 0;
        // 第一天有一次机会但是还没有股票
        dp[0][1][0] = 0;
        // 第一天手上有股票，可以进行两次交易
        dp[0][1][1] = -prices[0];
        // 当天手上有股票，还能买卖2次
        dp[0][2][1] = -prices[0];
        // 第一天有两次机会但是没股票
        dp[0][2][0] = 0;

        for (int i = 1; i < dp.length; i++) {
            // 没有机会交易但是有股票基本没戏
            dp[i][0][1] = Integer.MIN_VALUE;
            for (int k = dp_k; k >= 1; k--) {
                // 当天没有股票，昨天就没，或者昨天卖了
                dp[i][k][0] =  Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                // 当天有股票，昨天就有了或者昨天刚买的
                dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
            }
        }
        return dp[dp.length - 1][dp_k][0];
    }

    public int maxProfit_inf(int[] prices) {

        if (prices.length <= 1) {
            return 0;
        }
        int[][] dp = new int[prices.length][2];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < dp.length; i++) {
            // 这天没有股票，昨天卖了或者昨天就没有持有
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 当天手上有股票，昨天买的或者昨天就有了（这里就可以买，第一题k等于1不能卖）
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }

        return dp[dp.length - 1][0];
    }
}
